/*
 * @lc app=leetcode.cn id=236 lang=javascript
 *
 * [236] 二叉树的最近公共祖先
 */

// @lc code=start
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {TreeNode} root
 * @param {TreeNode} p
 * @param {TreeNode} q
 * @return {TreeNode}
 */
// 递归版
var lowestCommonAncestor = function(root, p, q) {
  let res = null
  const dfs = (node) => {
    if (!node) return false
    const lson = dfs(node.left)
    const rson = dfs(node.right)
    // p/q为祖先节点
    const isPOrQRoot = (node === p || node === q) && (lson || rson)
    // P/q不为祖先节点
    const isRoot = lson && rson
    if (isRoot || isPOrQRoot) {
      res = node
    }
    // 如果该分支找到了p/q那么返回true
    return lson || rson || (node === p || node ===q)
  }
  dfs(root)
  return res
}
// @lc code=end

// 迭代版
// var lowestCommonAncestor = function(root, p, q) {
//   let pRoot = p
//   let qRoot = q
//   let current = root
//   const stack = []
//   let prev = null
//   while (stack.length || current) {
//     while (current) {
//       stack.push(current)
//       current = current.left
//     }
//     current = stack.pop()
//     if (!current.right || current.right === prev) {
//       // 后序遍历才比较
//       if (current.left === pRoot || current.right === pRoot) {
//         pRoot = current
//       }
//       if (current.left === qRoot || current.right === qRoot) {
//         qRoot = current
//       }
//       if (pRoot === qRoot) return pRoot
//       prev = current
//       current = null
//     } else {
//       stack.push(current)
//       current = current.right
//     }
//   }
// };

